package com.leetcode.剑指offer专项突击版;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-02-28 19:59
 */
public class 剑指OfferII_007_数组中和为0的三个数 {


  static
  class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
      if (nums == null || nums.length < 2) {
        return new ArrayList<>();
      }

      Arrays.sort(nums);
      List<List<Integer>> answer = new ArrayList<>();
      for (int i = 0; i < nums.length; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) {
          continue;
        }
        int target = -1 * nums[i];
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
          if (nums[left] + nums[right] == target) {
            answer.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
          }
          if (nums[left] + nums[right] < target) {
            ++left;
            while (left < right && nums[left] == nums[left - 1]) {
              ++left;
            }
          } else {
            --right;
            while (left < right && nums[right] == nums[right + 1]) {
              --right;
            }
          }
        }
      }
      return answer;
    }
  }


}
